package Test.offer;

import java.util.ArrayList;

/**
 * @ClassName P57
 * @Description 和为s的两个数字
 * @Company inspur
 * @Author Kevin
 * @Date 2020/8/3 10:50
 * @Version 1.0
 */
public class P57 {
    /**
     * 双指针法，有序数列O(n)复杂度找
     */


    /**
     * 为s的连续正数序列
     */
    public ArrayList<ArrayList<Integer>> FindContinuesSequences(int sum) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if (sum <= 0) return list;

        int start = 1;
        int end = 2;
        int curSum = start + end;
        while (start < sum/2) {
            if (curSum < sum) {
                end++;
                curSum += end;
            } else if(curSum > sum) {
                curSum -= start;
                start++;
            } else {
                ArrayList<Integer> sequence = new ArrayList<>();
                for (int i = start; i <= end; i++) {
                    sequence.add(i);
                }
                list.add(sequence);

                curSum -= start;
                start++;
            }
        }
        return list;
    }
}
